1. Field of the Invention
The present invention generally relates to improving the performance of computer input/output (I/O) subsystems and, more particularly, to a practical solution to the so-called "File Assignment Problem" (FAP).
2. Description of the Prior Art
The FAP can be defined as follows: Suppose that one is given information on a computer system, including the configuration and performance characteristics of the I/O subsystem down through the Direct Access Storage Device (DASD) level. Suppose also that one is given statistics gathered on the access rates of the files (or some similar atomic unit of physical data) stored on those DASDs. Then a solution to the FAP is an assignment of the files to the DASDs which optimizes performance of the I/O subsystem over some reasonable period of time, while meeting appropriate system and user imposed constraints.
FIG. 1 shows an example of a typical computer I/O subsystem of contemporary design. Between the central processing unit (CPU) 10, which makes requests to read and write data, and the DASDs 11, on which the data is stored, is a hierarchy of shared components of varying intelligence. Collections of DASD 11 are attached serially to their (single) head of string (HOS) 12. These HOSs, in turn, are attached to one or more storage directors 13 of a controller. The storage directors are attached to one or more channels 14. Finally, the channels are attached to their single CPU 10 or a tightly coupled CPU complex. There will generally exist several paths connecting a given CPU to a given DASD. Additionally, some of the controllers may contain caches. Large computer systems may contain hundreds of DASDs.
The major motivation for solving the FAP is performance, and it can be summarized in the following three points:
(1) There is a clear and non-trivial performance gain to be had by achieving an optimally balanced file assignment as compared to a non-optimal assignment. Typical savings are in the range of 20 to 25%, in terms of mean I/O subsystem response time. The fact that I/O is a bottleneck to current computer system performance makes this observation all the more important.
(2) This non-optimal "skew" is not at all uncommon. For example, D. Hunter in "Modeling real DASD configurations", IBM Research Report RC 8606 (1980), has pointed out that even in "reasonably well-tuned systems" consisting of between 40 and 250 DASDs, it is "not uncommon that 90% of the non-paging DASD I/O requests go to 20% of the connected DASDs, or for 33% to go to just 3 of the connected DASDs".
(3) The FAP does not, in general, admit trivial solutions, and intuitive heuristics may very well lead to poor solutions. In one study by L. W. Dowdy and D. V. Foster entitled "Comparative models of the File Assignment Problem", ACM Computer Surveys, vol. 14, no. 2, (1982), "eight researchers with doctorates in computer science studied" a prototypical FAP, and "gave eyeball solutions". These solutions averaged "4% below an average randomly chosen file assignment, and 36% below the optimal file assignment". Thus, a more sophisticated approach to the FAP would seem to be essential.
Given this state of affairs, it should not be surprising that the computer science literature is filled with papers on the FAP, and in fact this is the case. In addition to the survey paper of Dowdy and Foster, see for example B. W. Wah, "File Placement on Distributed Computer System", Computer (1984) and U.S. Pat. No. 4,542,458 to Kitajima et al. Unfortunately, these are primarily of theoretical interest, and a real-world, practical solution to the FAP has been elusive.